import java.util.Queue;
import java.util.HashSet;
import java.util.Random;
import java.util.Comparator;
import java.util.Iterator;
import java.lang.IllegalArgumentException;

public class PriorityQueueTest {
	
	
	/**
	 * This class will help you test your priority queue. Although it is quite comprehensive
	 * feel free to write your own tests. The program will exit on an assertion error, so to
	 * test the methods, comment out the ones which you are failing on and test the rest.
	 */
	public static void main(String[] args){
		PriorityQueueTest pqt = new PriorityQueueTest();
		pqt.testOffer();
		pqt.testOrdering();
		pqt.testOrdering2();
		pqt.testComparator();
		pqt.testIterator();
		pqt.exceptionTest1();
		pqt.exceptionTest2();
		pqt.exceptionTest3();
		System.out.println("Everything works fine. Well done.");
	}
	
	public void testOffer ()
	{
		Queue <String> pq = new PriorityQueue <String> ();
		boolean ret = pq.offer ("blah");
		assertEquals ("offer on queue returns true", true, ret);
		assertEquals ("size on queue returns 1 after insert", pq.size (), 1);	
	}
	
	public void testOrdering()
	{
		Queue<Double> pq = new PriorityQueue<Double> ();
		Random rng = new Random();
		for (int i = 0; i < 20000; i++){
			pq.offer(rng.nextDouble() + 1);
		}
		pq.offer(0.01);
		for (int i = 0; i < 20000; i++){
			pq.offer(rng.nextDouble() + 1);
		}
		assertEquals("ordering in pq is incorrect", 0.01, pq.poll());
	}
	
	public void testOrdering2()
	{
		Queue<Integer> pq = new PriorityQueue<Integer> ();
		Random rng = new Random();
		for (int i = 0; i < 100000; i++){
			pq.offer(rng.nextInt());
		}
		Integer lastInt = pq.poll();
		while (!pq.isEmpty()){
			Integer nextInt = pq.poll();
			assertTrue("Lower numbers should always be returned first", lastInt <= nextInt);
			lastInt = nextInt;
		}
	}
	
	public void testComparator()
	{
		Comparator<String> comp = new Comparator<String> (){
			// a comparator such that "guna" is always ranked first
			public int compare(String a, String b){
				if (a == b) return 0;
				if (a == null || b == null) throw new ClassCastException();
				if (a.equals("guna")) return -1;
				else if (b.equals("guna")) return 1;
				else return (a.compareTo(b));
			}
		};
		Random rng = new Random();
		Queue<String> pq = new PriorityQueue<String> (200, comp);
		for (int i = 0; i < 20000; i++){
			char q = (char)rng.nextInt(256);
			char r = (char)rng.nextInt(256);
			String s = q + r + ";";
			pq.offer(s);
			if (i == 10000) pq.offer("guna");
		}
		assertEquals("comparator does not behave as expected", "guna", pq.poll());
	}
	
	
	public void testIterator(){
		Queue<Integer> pq = new PriorityQueue<Integer> (1);
		for (int i = 0; i < 100; i++){
			pq.offer(i);
		}
		boolean[] b = new boolean[100];
		java.util.Arrays.fill(b, false);
		Iterator<Integer> itr = pq.iterator();
		while (itr.hasNext()){
			b[itr.next()] = true;
		}
		for (boolean bool : b){
			assertTrue("iterator returned all elements in pq", bool);
		}
	}
		
	
	public void exceptionTest1(){
		try {
			Queue<Integer>pq = new PriorityQueue<Integer>(0);
		} catch (Exception e){
			if (e.getClass() != IllegalArgumentException.class){
				System.out.println("Required exception not thrown : IllegalArgumentException");
			}
		}
	}
	
	public void exceptionTest2(){
		try {
			Queue<Object>pq = new PriorityQueue<Object>();
			pq.offer(new Object());
			pq.offer(new Object());
		} catch (Exception e){
			if (e.getClass() != ClassCastException.class){
				System.out.println("Required exception not thrown: ClassCastException");
			}
		}
	}
	
	public void exceptionTest3(){
		try {
			Queue<Comparable> pq = new PriorityQueue<Comparable>();
			pq.offer(null);
		} catch (Exception e){
			if (e.getClass() != NullPointerException.class){
				System.out.println("Required exception not thrown : NullPointerException");
			}
		}
	}
	
	
	public static void assertTrue(boolean b){
		assertTrue("", b);
	}
	
	public static void assertTrue(String s, boolean b){
		if (!b) {
			System.out.println("Assertion error: " + s + " Expected true was false.");
			System.exit(1);
		}
	}
	
	public static void assertEquals(Object a, Object b){
		assertEquals("", a, b);
	}
	
	public static void assertEquals(String s, Object a, Object b){
		if (a == null && b == null) return;
		if (a != null && b != null){
			if (a.equals(b)) return;
		}
		System.out.println("Assertion error: " + s + " Expected " + a + " was " + b);
		System.exit(1);
	}
}
